package 动态规划;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/2 20:25
 */
public class leetcode115不同的子序列 {

    /*
     为什么 这个代码 能 达到 1ms
     这是我非常 不理解的地方
     */
    class Solution {
        Integer[][] memo;
        public int numDistinct(String s, String t) {
            int sLen = s.length(), tLen = t.length();
            memo = new Integer[tLen][sLen];

            return dfs(s, t, s.length() - 1, t.length() - 1);
        }
        private int dfs(String s, String t, int sIndex, int tIndex) {//递归作用，缩小规划，好分析边界，解决问题
            if (tIndex < 0) return 1;  //t的索引小于零了，那么就找到了
            if (sIndex < 0) return 0;

            if (sIndex < tIndex) return 0; // <3> 优化3， 12ms --> 2ms 这里表示s的长度都小于t了，那么就是没找到

            if (memo[tIndex][sIndex] != null) return memo[tIndex][sIndex];//以前算过了，直接返回
            //没算过就去算
            int ans = 0;
            if (s.charAt(sIndex) == t.charAt(tIndex)) ans += dfs(s, t, sIndex - 1, tIndex - 1);
            ans += dfs(s, t, sIndex - 1, tIndex);//匹配时，可选，可不选。, //不匹配时，只能不选,

            memo[tIndex][sIndex] = ans;  //memo记录动态规划的dp数组
            return ans;
        }
    }


    public static void main(String[] args) {
        String s = "babgbag";
        String t = "bag";

//        System.out.println(recursion(0,0,s,t));
        System.out.println(solution(s,t,0));
//        System.out.println(count);
//        System.out.println(recursionBinary(0,0,s,t));
        System.out.println(dp(s,t));
//        Character.isDigit()
        char c = '0' - 1;
        System.out.println((int)c);
        System.out.println((int)'0');
    }


    /*
    ***   样本的对应模型 ****
    有点类似于最长公共子序列
    这个题 受到了 很多的启发

    从背包的 角度 去考虑就行了
    在 choose 的 编码 有些不一样!
    从某种角度 来看这就是个 背包问题

    从 s 中 按照 字符串的相对 顺序 选出 字符
    组成  t ,这不就是 一个 背包问题嘛

    这道题 真的 能 引发 更高的 一个思考
    最关键的 核心在于  从 当前层 递归
    进入 下一层 递归 时. 该以 什么样的 一个 状态 进入 下一层递归!
     */
    public static int solutionMemory(String s,String t){
        int dp[][] = new int[s.length() + 1][t.length() + 1];
        for(int i = 0;i <= s.length();i++){
            Arrays.fill(dp[i], -1);
        }
        return recursionBinary(0,0,s,t,dp);
    }



  //二叉树递归 记忆化搜索 加 优化  3 ms .既然 比 dp 快 ,这是  我 没想到的
    public static int recursionBinary(int indexS,int indexT,String s,String t,int dp[][]){
        if(indexT == t.length()){
            return dp[indexS][indexT] = 1;
        }
        if(s.length() - indexS < t.length() - indexT)
            return 0;
        if(indexS == s.length()){
            return dp[indexS][indexT] = 0;
        }
        if(dp[indexS][indexT] != -1)
            return dp[indexS][indexT];
        int ans = 0;
        if(s.charAt(indexS) == t.charAt(indexT)){
            ans = recursionBinary(indexS + 1,indexT + 1,s,t,dp);
        }
        //no choose
        ans += recursionBinary(indexS + 1,indexT,s,t,dp);
        return dp[indexS][indexT] = ans;
    }


 // dp 10 ms
    // 这已经优化到 极致了吧 .从 dp 的层面上
    public static int dp(String s,String t){
        int sLen = s.length();
        int tLen = t.length();
        int [][]dp = new int[sLen + 1][tLen + 1];
        dp[sLen][tLen] = 1;
        for(int indexS = sLen - 1;indexS >= 0;indexS--){
            dp[indexS][t.length()] = 1;
            for(int indexT = tLen - 1;indexT >= 0 ;indexT --){
                // 小小的 优化 的 地方 ***************************
                 // 这里的优化 有点 小错误, 应该 是  长度 比较 不是 索引 比较
                // 这样得到的 才是 长度!
                if(sLen - indexS < tLen - indexT)
                    break;
                if(s.charAt(indexS) == t.charAt(indexT)){
                    dp[indexS][indexT] = dp[indexS + 1][indexT + 1];
                }
                dp[indexS][indexT] += dp[indexS + 1][indexT];
            }
        }
        return dp[0][0];
    }










    /*
     虽然 过了 ,但是  时间 O(N ^ 3) 2280ms
     主要是 在 求 dp[][] 的过程中 ,有个 for枚举 的过程
     这种题 写的 也多了,这是 一种多叉树 版本的递归
     那 递归中肯定是有一个 for循环的
     如果 我们能把 多叉树 改成 二叉树 递归
     那就直接 优化掉 一个 for 循环 (注意 一下 什么 时候应该枚举 ,什么时候 不用枚举)
     思考 爬 楼梯 问题
     当前层 递归 ,可以 选择 一次 走 1 ,2 ,3 , 4 ,x 步
     这就需要枚举了 但我也可以不 使用 for
     一个一个 列出来 完 也可以(编码 不优雅)
      */
    public static int solution(String s,String t,int ego){
        int sLen = s.length();
        int tLen = t.length();
        if(tLen == 0)
            return 0;
        int [][] dp = new int [sLen + 1][tLen + 1];
        for(int i = 0;i < sLen;i++ ){
            Arrays.fill(dp[i], -1);
        }

        return recursion(0,0,s,t,dp);
    }
    public static int recursion(int indexS,int indexT,String s,String t,int dp[][]){
        if(indexT == t.length()){
            return  dp[indexS][indexT] = 1;
        }
        if(dp[indexS][indexT] != -1){
            return dp[indexS][indexT];
        }
        int ans = 0;
        for(int i = indexS;i < s.length();i++){
            if(s.charAt(i) == t.charAt(indexT)){
                ans += recursion(i + 1,indexT + 1,s,t,dp);
            }
        }
        return dp[indexS][indexT] = ans;
    }


/*
        这种版本 超时了
        主要是 因为  在 dp [][] 数组 判断的时候 有些  瑕疵
        dp[indexS][indexT] = 0 有点 模棱两可
        可能是 没计算过,但也可能 是 计算的 值 就是 0
        所以 这一步 也造成 一些 重复的 计算的过程
 */
    public static int solutionOne(String s,String t){
        int sLen = s.length();
        int tLen = t.length();
        if(tLen == 0)
            return 0;
        int [][] dp = new int [sLen + 1][tLen + 1];
//        for(int i = 0;i < sLen;i++ ){
//            Arrays.fill(dp[i], -1);
//        }

        return recursionOne(0,0,s,t,dp);
    }
    public static int recursionOne(int indexS,int indexT,String s,String t,int dp[][]){
        if(indexT == t.length()){
            return  dp[indexS][indexT] = 1;
        }
        if(dp[indexS][indexT] != 0){
            return dp[indexS][indexT];
        }
        int ans = 0;
        for(int i = indexS;i < s.length();i++){
            if(s.charAt(i) == t.charAt(indexT)){
                ans += recursionOne(i + 1,indexT + 1,s,t,dp);
            }
        }
        return dp[indexS][indexT] = ans;
    }




    /*
    在写暴力递归之前能不能 先分析 一下
    该 暴力递归能不能优化成 记忆化搜索， 和 dp
    这个 题 优化不了 肯定超时的
    参数 sb 突破了 整型 的范围
    那只能换思路了！
    超时 版本！
     */
    public static int solution(String s,String t){
        int len = s.length();
        if(t.length() == 0)
            return 0;
        return recursion(0,new StringBuilder(),t,s,len);
    }
    public static int recursion(int index,StringBuilder sb,String t,String s,int len){
        if(sb.length() == t.length()){
            return sb.toString().equals(t) ? 1 : 0;
        }
        if(index == len)
            return 0;
        int ans = 0;
        // choose
        sb.append(s.charAt(index));
        ans = recursion(index + 1,sb,t,s,len);
        sb.deleteCharAt(sb.length() - 1);
        // no choose
        ans += recursion(index + 1,sb,t,s,len);
        return ans;
    }

    @Test
    public void test(){
        /*
         牛逼池化的操作比较居然 还慢些 ， 卧槽
         Jvm 肯定做了一些的优化
         */
        StringBuilder sb = new StringBuilder();
        Random random = new Random();
        for(int i = 0;i < 10000;i++){
            sb.append((char)('a' + random.nextInt(26)));
        }
        String intern = sb.toString().intern();
        String s = sb.toString();
        String sc = sb.toString();
        long l = System.currentTimeMillis();
        boolean equals = false;
        for(int i = 0;i < 10000;i++){
            equals = s.equals(sc);
        }
        long l1 = System.currentTimeMillis();
        System.out.println(equals);
        System.out.println(l1 - l);
        long l2 = System.currentTimeMillis();
        boolean b = false;
        String intern1 = s.intern();
        for(int i = 0;i < 1000000000;i++){
            b = intern == intern1;
        }
        long l3 = System.currentTimeMillis();
        System.out.println(b);
        System.out.println(l3 - l2);
    }

    @Test
    public void testIntern(){
        /*
          注意 new String （str） ；这个返回的引用 是在 堆中的
          而 “abcdefg” 这种引用 是在 字符串常量池的
          s.intern(); 返回一个 引用，如果 串池中 有 s 则返回 串池中 s 的 引用
          如果不存在 ，则 把 s 加入串池，并返回其 在串池的引用！
         */
        StringBuilder sb = new StringBuilder("hello");
        System.out.println(sb.toString() == sb.toString());
        String intern = sb.toString().intern();
        String s2 = new String("hello");
        String s3 = s2.intern();
        System.out.println(s2 == s3);// t
        String intern1 = "hello".intern();
        String s = "hello";
        String s1 = "hello";
        System.out.println(s3==s);
        System.out.println(intern1 == s);// t
        System.out.println(intern == intern1); //t
        System.out.println(intern == s2);//f
        System.out.println(s == s2);//f
        System.out.println(s == sb.toString());//f
    }






}
